`
https://leetcode.cn/problems/smallest-range-covering-elements-from-k-lists/
`

/**
 * @param {number[][]} nums
 * @return {number[]}
 */
var smallestRange = function (nums) {
  // 将 k 个列表都合并并排序，记录所在的原数组索引
  // 求最短的包含 k 个序列索引的子数组的左右端点

  const k = nums.length
  // 合并 k 个有序列表
  // [ {list, idx}, ... ]
  const pq = new Heap((a, b) => b.list.at(-1) - a.list.at(-1))
  // [ [val, idx], ... ]
  const ns = []
  for (let i = 0; i < k; i++) {
    const l = nums[i]
    pq.push({ list: l, idx: i })
  }
  while (!pq.isEmpty()) {
    const l = pq.pop()
    ns.push([l.list.pop(), l.idx])
    if (l.list.length) pq.push(l)
  }
  // 为了避免从头拿导致的 O(n) 使用倒序，这里翻转回来
  ns.reverse()

  // 滑动窗口
  const n = ns.length
  // 每个列表里的数字在窗口内出现的次数
  const cnt = new Array(k).fill(0)
  // 窗口d 数字来源于多少个列表
  let count = 0
  let left = 0, right = 0
  let resL = -Infinity, resR = Infinity

  while (right < n) {
    const [n1, i1] = ns[right++]
    cnt[i1]++
    if (cnt[i1] === 1) count++

    // 窗口里包含了 k 个列表里的值时更新答案
    while (count >= k) {
      const targetL = ns[left][0]
      const targetR = ns[right - 1][0]
      if (targetR - targetL < resR - resL) {
        resL = targetL
        resR = targetR
      }
      const [n2, i2] = ns[left++]
      cnt[i2]--
      if (cnt[i2] === 0) count--
    }
  }

  return [resL, resR]
};